Grokking Oracle Coding Interview
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Who Should Take This Course?
Oracle Easy
Count Number of Pairs With Absolute Difference K (easy)
Solution: Count Number of Pairs With Absolute Difference K
Degree of an Array (easy)
Solution: Degree of an Array
Find Subsequence of Length K With the Largest Sum (easy)
Solution: Find Subsequence of Length K With the Largest Sum
Rectangle Overlap (easy)
Solution: Rectangle Overlap
Remove All Adjacent Duplicates In String (easy)
Solution: Remove All Adjacent Duplicates In String
Island Perimeter (easy)
Solution: Island Perimeter
Climbing Stairs (easy)
Solution: Climbing Stairs
Move Zeroes (easy)
Solution: Move Zeroes
Excel Sheet Column Title (easy)
Solution: Excel Sheet Column Title
Valid Parentheses (Easy)
Solution: Valid Parentheses
Oracle Medium
Longest Palindromic Substring (medium)
Solution: Longest Palindromic Substring
Single Element in a Sorted Array (medium)
Solution: Single Element in a Sorted Array
Pairs of Songs With Total Durations Divisible by 60 (medium)
Solution: Pairs of Songs With Total Durations Divisible by 60
Search a 2D Matrix II (medium)
Solution: Search a 2D Matrix II
Minimize Maximum of Array (medium)
Solution: Minimize Maximum of Array
Asteroid Collision (medium)
Solution: Asteroid Collision
Combination Sum (medium)
Solution: Combination Sum
Binary Tree Right Side View (medium)
Solution: Binary Tree Right Side View
Sort Colors (medium)
Solution: Sort Colors
Group Anagrams (Medium)
Solution: Group Anagrams
Decode String (Medium)
Solution: Decode String
Number of Islands (medium)
Solution: Number of Islands
Binary Tree Zigzag Level Order Traversal (medium)
Solution: Binary Tree Zigzag Level Order Traversal
Longest Common Subsequence (medium)
Solution: Longest Common Subsequence
Rotting Oranges (medium)
Solution: Rotting Oranges
Meeting Rooms II (medium)
Solution: Meeting Rooms II
Delete Node in a BST (medium)
Solution: Delete Node in a BST
Remove Duplicate Letters (medium)
Solution: Remove Duplicate Letters
Longest Substring Without Repeating Characters (medium)
Solution: Longest Substring Without Repeating Characters (medium)
Search in Rotated Array (medium)
Solution: Search in Rotated Array
Spiral Matrix (medium)
Solution: Spiral Matrix
Container With Most Water (Medium)
Solution: Container With Most Water
3Sum (medium)
Solution: 3Sum
Simplify Path (medium)
Solution: Simplify Path
Next Permutation (medium)
Solution: Next Permutation
Basic Calculator II (medium)
Solution: Basic Calculator II
Merge Intervals (medium)
Solution: Merge Intervals
Restore IP Addresses (medium)
Solution: Restore IP Addresses
Longest Increasing Subsequence (medium)
Solution: Longest Increasing Subsequence
Validate Binary Search Tree (medium)
Solution: Validate Binary Search Tree
Oracle Hard
Integer to English Words (hard)
Solution: Integer to English Words
Trapping Rain Water (hard)
Solution: Trapping Rain Water
First Missing Positive (hard)
Solution: First Missing Positive
Merge K Sorted Lists (hard)
Solution: Merge K Sorted Lists
Max Points on a Line (hard)
Solution: Max Points on a Line
Sudoku Solver (hard)
Solution: Sudoku Solver
Longest Valid Parentheses (hard)
Solution: Longest Valid Parentheses
Remove Nth Node From End of List (Medium)
Solution: Remove Nth Node From End of List
Median of Two Sorted Arrays (hard)
Solution: Median of Two Sorted Arrays
Constrained Subsequence Sum (hard)
Solution: Constrained Subsequence Sum
Solution: Constrained Subsequence Sum

Problem Statement

Given an array arr containing integers and an integer k, return the maximum sum of a non-empty subsequence of arr array such that for every two adjacent integers in the subsequence, arr[i] and arr[j], where i < j, the condition j - i <= k is satisfied.

A subsequence of the array is obtained by removing some elements (may be zero) from the array, leaving the remaining elements in their original order.

Examples

Example 1:

  • Input: arr = [10, -2, -10, 5], k = 2
  • Expected Output: 13
  • Explanation: The subsequence [10, -2, 5] has a maximum sum 13, which follows the given rules.

Example 2:

  • Input: arr = [3, 2, 1, -5], k = 1
  • Expected Output: 6
  • Explanation: The subsequence [3, 2, 1] has a maximum sum, which follows the given rules.

Example 3:

  • Input: arr = [3, 2, 7, -5, 10], k = 2
  • Expected Output: 22
  • Explanation: The optimal subsequence to choose is [3, 2, 7, 10]. Starting with 3, then pick 2 and 7, and finally, skip -5(negative number) and pick 10, resulting in the maximum sum of 22.

Solution

To solve this problem, we'll leverage a dynamic programming approach with a sliding window technique, enhanced by a deque to efficiently manage the k constraint. The essence of our approach is to maintain a list of potential candidates for each position in a way that allows us to quickly find the maximum sum up to that point, considering the constraint that we cannot pick two elements greater than k positions apart. We believe this approach works effectively because it combines the robustness of dynamic programming in handling subproblems (finding the maximum sum up to each point) with the efficiency of a deque in maintaining the maximum value within the sliding window of the last k elements. This method ensures that we always have quick access to the best candidate for the next step in our sequence, optimizing both time and space usage.

By keeping track of the maximum sums in a dynamic manner and pruning non-viable options using the deque, we ensure that our algorithm remains both efficient and straightforward. The sliding window deque helps us avoid recalculating sums for elements that are too far apart to be included in the same subsequence, thereby significantly reducing the computational overhead. This blend of dynamic programming for subproblem optimization and deque for efficient constraint management makes our approach the most effective for tackling the problem.

Step-by-step algorithm

  • Initialize a dynamic array dp of the same length as the input array arr to store the maximum sum up to each index.
  • Initialize a deque to maintain the indices of potential candidates for the maximum sum, ensuring that the deque always represents the best choices within the last k elements.
  • Iterate through arr, and for each element at index i:
    • Calculate dp[i] as the maximum of arr[i] and arr[i] + dp[deque.front()], which represents either taking the current element by itself or adding it to the sum of the best subsequence ending k or less elements before.
    • While the deque is not empty and dp[i] is greater than dp[deque.back()], pop elements from the back of the deque. This step ensures that the deque always contains the indices of elements that are potential candidates for forming the maximum sum.
    • If any indices in the deque are more than k steps away from i, remove them from the front. This action maintains the constraint that any two elements in the subsequence must be at least k places apart.
    • Push the current index i onto the back of the deque.
  • The answer to the problem is the maximum value in the dp array.

Algorithm Walkthrough

Let's consider the input arr = [3, 2, 7, -5, 10] with k = 2.

Initial Setup

  • Input Array (arr): [3, 2, 7, -5, 10]
  • Constraint (k): 2
  • Dynamic Programming Array (dp): Initialized to [0, 0, 0, 0, 0] (same length as arr).
  • Deque (dq): An empty deque to keep track of indices with potential maximum sums.

Iteration 1: Index 0 (Value = 3)

  • dp[0] is set to arr[0] which is 3. dp = [3, 0, 0, 0, 0].
  • Deque is updated to [0].
  • Maximum sum so far is 3.

Iteration 2: Index 1 (Value = 2)

  • Calculate dp[1]: The deque contains 0 at its front, so dp[1] = max(arr[1], dp[deque.front()] + arr[1]) = max(2, 3 + 2) = 5.
  • dp = [3, 5, 0, 0, 0]
  • Update deque: dp[1] > dp[0]. So, pop 0 from the queue.
  • Deque becomes [1].
  • Maximum sum so far is 5.

Iteration 3: Index 2 (Value = 7)

  • Calculate dp[2]: The deque contains 1 at its front, so dp[2] = max(arr[2], dp[deque.front()] + arr[2]) = max(7, 5 + 7) = 12.
  • dp = [3, 5, 12, 0, 0]
  • Update deque: dp[2] > dp[1]. So, pop 1 from the queue.
  • Deque becomes [2].
  • Maximum sum so far is 12.

Iteration 4: Index 3 (Value = -5)

  • Calculate dp[3]: The deque contains 2 at its front, so dp[3] = max(arr[3], dp[deque.front()] + arr[3]) = max(-5, 12 + -5) = 7.
  • dp = [3, 5, 12, 7, 0]
  • Update deque: dp[3] < dp[2]. So, We don't need to perform the pop operation in the queue.
  • Push 3 in the Deque. Deque becomes [2, 3].
  • Maximum sum so far is 12.

Iteration 5: Index 4 (Value = 10)

  • Calculate dp[4]: The deque contains 1 at its front, so dp[4] = max(arr[4], dp[deque.front()] + arr[4]) = max(10, 12 + 10) = 22.
  • dp = [3, 5, 12, 7, 22]
  • Update deque: dp[4] > dp[3]. So, pop 3 from the queue.
  • Update deque: dp[4] > dp[2]. So, pop 2 from the queue.
  • Deque becomes [].
  • Maximum sum so far is 22.

Conclusion

  • The maximum sum is 22.

Code

Java
Saved to Cloud

. . . .

Complexity Analysis

Time Complexity

  • : The algorithm iterates through each element of the input array exactly once. During each iteration, the operations performed (such as updating the dynamic programming array dp, and adding/removing elements from the deque) are constant time operations, assuming that deque operations (pushBack, popFront, popBack) are O(1). Therefore, the overall time complexity is linear with respect to the length of the input array, n.

Space Complexity

  • : The space complexity is primarily dictated by the size of the dynamic programming array dp, which stores the maximum sum that can be obtained up to each index. This array has the same length as the input array, so the space complexity is . Additionally, the deque used for optimizing the search for the maximum within a sliding window can, in the worst case, store an index for each element in the array. However, this does not change the overall space complexity, which remains linear with respect to the input size.
Constrained Subsequence Sum (hard)
Mark as Completed

On this page

Problem Statement

Examples

Solution

Step-by-step algorithm

Algorithm Walkthrough

Code

Complexity Analysis

Time Complexity

Space Complexity